package chapter11;

/**
 * 散列表
 */
public class HashTable {

    public static Node directAddressSearch(Node[] T, int k) {
        return T[k];
    }

    public static void directAddressInsert(Node[] T, Node x) {
        T[x.key] = x;
    }

    public static void directAddressDelete(Node[] T, Node x) {
        T[x.key] = null;
    }

    /**
     * 哈希策略的一种
     *
     * @param v
     * @param l
     * @return
     */
    public static int h(int v, int l) {
        return Math.floorMod(v, l);
    }

    public static void chainedHashInsert(Node[] T, Node x) {
        int h = h(x.key, T.length);
        if (T[h] != null) {
            x.parent = T[h].parent;
            x.next = T[h];
        }
        T[h] = x;
    }

    public static Node chainedHashSearch(Node[] T, int k) {
        int h = h(k, T.length);
        if (T[h] != null) {
            Node node = T[h];
            while (node != null && node.key != k) {
                node = node.next;
            }
            return node;
        }
        return null;
    }

    public static void chainedHashDelete(Node[] T, Node x) {
        int h = h(x.key, T.length);
        if (T[h] != null) {
            Node node = T[h];
            while (node != null && node.key != x.key) {
                node = node.next;
            }
            if (node != null) {
                node.parent.next = node.next;
            }
        }
    }

    static class Node {
        public Node parent;
        public int key;
        public Node next;

        public Node() {
        }

        public Node(int key) {
            this.key = key;
        }
    }

}
